#[test]
fn test_max_number() {
    let v1 =vec![3, 2, 3];
    let v2 = vec![3, 2, 4];
    // let v3 = vec![v1, v2];
    // println!("{:?}", v3.iter().max().unwrap());

    // println!("{:?}", max_subsequence(&vec![4, 1, 1, 2, 3], 2));

    // println!("{:?}", max_number(vec![3,4,6,5], vec![9,1,2,5,8,3], 5));

    println!("{}", lexicographical_less(&v1, &v2));
    println!("{}", v1[..] < v2[..]); // slice compare
}

// 321
fn max_number(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<i32> {
    // 选取nums1 nums2中分别长度为x和y的两个最大子序列，
    // 将两个子序列最大化合并
    // 枚举所有的序列长度l1+l2 = k
    let m = nums1.len();
    let n = nums2.len();

    let ans = (0.max(k - n as i32)..=(m as i32).min(k))
                .map(|l| merge_two_sequence(&max_subsequence(&nums1, l as usize), &max_subsequence(&nums2, k as usize - l as usize)))
                .max().unwrap();

    return ans;
}

// 使用单调栈求最大子序列
fn max_subsequence(nums: &Vec<i32>, l: usize) -> Vec<i32> {
    let mut stack: Vec<i32>= vec![];
    for (i, v) in nums.iter().enumerate() {
        while stack.len() > 0 && stack.len() + nums.len() - i - 1 >= l && v > stack.last().unwrap() {
            stack.pop();
        }
        if stack.len() < l {
            stack.push(*v);
        }
    }
    return stack;
}

fn merge_two_sequence(nums1: &Vec<i32>, nums2: &Vec<i32>) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    let (mut i, mut j) = (0, 0);
    while i < nums1.len() && j < nums2.len() {
        if nums1[i..] < nums2[j..] {  // 注意，这里比较的是两个slice（即先比较当前nums1[i],nums2[j]两个数字，如果相等，则比较两个序列整体的大小）
            res.push(nums2[j]);
            j += 1;
        } else {
            res.push(nums1[i]);
            i += 1;
        }
    }
    res.extend(&nums1[i..]);
    res.extend(&nums2[j..]);
    res
}

// return true if nums1 < nums2
// the same result of nums1[..] < nums2[..]
fn lexicographical_less(nums1: &Vec<i32>, nums2: &Vec<i32>) -> bool {
    let mut i = 0;
    while i < nums1.len() && i < nums2.len() {
        if nums1[i] != nums2[i] {
            return nums1[i] < nums2[i];
        }
        i += 1;
    }
    return nums1.len() < nums2.len();
}